package Algorithom.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 *  merge sort
 *
 * @Author Sven
 */
public class MergeSort {

    public static void main(String[] args) {

        int[] data = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50};

        mergeSort(data, 0, data.length - 1);

        System.out.println("排序结果：" + Arrays.toString(data));
    }

    private static void mergeSort(int[] data, int low, int high) {
        int mid = (low + high) / 2;

        if (low < high) {
            //left
            mergeSort(data, low, mid);

            //right
            mergeSort(data, mid + 1, high);

            //merge left and right
            merge(data, low, mid, high);

            System.out.println(Arrays.toString(data)+" low="+data[low]+" mid="+data[mid]+" high="+data[high]);
        }
    }

    private static void merge(int[] data, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;
        int j = mid + 1;
        int k = 0;


        //put the smaller number to the new temp
        while (i <= mid && j <= high) {
            if (data[i] < data[j]) {
                temp[k++] = data[i++];
            } else {
                temp[k++] = data[j++];
            }
        }

        //put the rest of the left to the temp
        while (i <= mid) {
            temp[k++] = data[i++];
        }


        //put the rest of the right to the temp
        while (j <= high) {
            temp[k++] = data[j++];
        }
        //override the data array
        for (int k2 = 0; k2 < temp.length; k2++) {
            data[k2 + low] = temp[k2];
        }

    }


    @Test
    public void test() {

        int[] array = {1, 2, 3, 4, 5, 6};

        int i = 0;

        System.out.println(array[i]);     //先执行 array[i] 再进行自增操作
        System.out.println(array[i++]);


    }
}
